#include <iostream>
#include <cctype>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
        // 对于第二个肯定是不能变动的，所以只能对其下标进行排序
        vector<int> index(nums2.size());
        for(int i = 0; i < nums2.size(); ++i)
            index[i] = i;
        sort(index.begin(), index.end(), [&](int a, int b){
            return nums2[a] < nums2[b];
        });
        sort(nums1.begin(), nums1.end());
        // 田忌赛马，如果最差的能够比过对面最差的，那就放进去
        // 可以证明每次和最小的比即可
        vector<int> ans(nums1.size());
        for(int pos = 0, l = 0, r = nums1.size() - 1; pos < nums1.size(); ++pos)
        {
            if(nums1[pos] > nums2[index[l]])
            {
                ans[index[l++]] = nums1[pos];
            }
            else
                ans[index[r--]] = nums1[pos];
        }

        return ans;
    }
};